perm filename TMP[CAR,BGB] blob
sn#019087 filedate 1973-01-10 generic text, type T, neo UTF8
00100 SAILON NUMBER 71. DRAFT CRE MANUAL.
00200
00300
00400 STANFORD ARTIFICIAL INTELLIGENCE LABORATORY JANUARY 1973.
00500 OPERATING NOTE NUMBER 71.
00600
00700
00800
00900 - - - DRAFT - - -
01000 Contour-Region-Edge Image Representation.
01100
01200
01300 Bruce g. Baumgart
01400
01500
01600 ABSTRACT:
01700
01800 A contour-region-edge, CRE, image representation is stated
01900 and an algorithm for converting a digital television image into this
02000 format is explained. An implementation of the algorithm is the main
02100 routine of a program called Cart's Eye, CRE; auxiliary routines of
02200 CRE provide manual cart control, TV camera input, and image display.
02300 Potential application of CRE as a step in object perception and
02400 vehicle control is discussed.
02500
02600
02700 CONTENTS:
02800
02900 I.
02950 A. DATA STRUCTURE.
03000 B. THE ALGORITHM.
03100 C. PERFORMANCE.
03300 II.
03350 A. TELETYPE COMMANDS.
03400 B. FILE FORMATS.
03500 C. LISP AND SAIL INTERFACING.
03700 III.
03750 A. EDITORIAL REMARKS.
03800 B. CODE DOCUMENTATION.
03900 C. APPENDICES.
04000
04100
04200 This research was supported by the Advanced Research Projects Agency
04300 of the Office of the Secretary of Defense under contract SD-183.
00100 INTRODUCTION.
00200
00300
00400 Cart's eye does three things: first, it inputs a series of
00500 digital television pictures; second, it converts the pictures into a
00600 contour-region-edge data structure; and third, it outputs its data
00700 structure into a disk file. The process is automatic and is intended
00800 to run without human intervention. Furthermore, the process is
00900 "bottom up"; there are no significant inputs other than the given
01000 television images. The design goal was to provide video image input
01005 data in a form appropriate for my geometric editor, GEOMED.
01010
01100
01200
01300 I. A. DATA STRUCTURE.
01400
01500
01600 Contour-Region-Edge or CRE, is a combination of ideas; the
01700 two principle idea being that of an elevation contour map and that of
01800 a political map. On a contour map of a continent fully surrounded by
01900 ocean, no two contour lines every cross and all the contour lines
02000 close. Consequently, the loops of elevation contours enclose
02100 regions; and these regions overlap in a nested fashion forming a tree
02200 data structure. On political maps, ignoring for the moment geographic
02300 pathologies such as Vietnam and the Vatican; no two states ever
02400 overlap, the states are bounded by borders, and the regions within
02500 the borders are simply connected.
02600
02700 One principle idea that is emphatically not in CRE is that of
02800 a schematic or artist line drawing. Although the CRE output can
02900 be viewed as a collection of lines on a display screen, people
03000 expecting an artistic line drawing redition of the given television
03100 picture will be disappointed. A CRE picture from CRE is a simple
03200 translation of the photometry, geometry and topology of the orginal
03300 video image. Whereas a pure line drawing from a human illustrator is
03400 a more complicated symbolic representation of the scene without
03500 photometric information.
03600
03700 The data structure to be discussed is implemented as small
03800 blocks of words containing pointers and data in the fashion usual to
03900 graphics and simulation; an introduction to this technology can be
04000 found in Knuth [1]. The language of implementation is PDP-10 machine
04100 code, via the FAIL assembler.
00100 VECTOR/ARC/VERTEX.
00200
00300 _____________________________________________
00400 word | CW | CCW |
00500 0 | vector ring |
00600 _____|___________________|___________________|
00700 word | ROW | COL |
00800 1 | ∂ 0000.00 | ∂ 0000.00 |
00900 _____|___________________|___________________|
01000 word | TYPE | RELOC |
01100 2 | ∂ 1 | ∂ 303 313 |
01200 _____|___________________|___________________|
01300 word | | |
01400 3 | ENDO | EXO |
01500 _____|___________________|___________________|
01600 word | | |
01700 4 | ARC | PED |
01800 _____|___________________|___________________|
01900 word | | |
02000 5 | ∂ CNTRST | PGON |
02100 _____|___________________|___________________|
02200 word | | |
02300 6 | NTIME | PTIME |
02400 _____|___________________|___________________|
02500
02600
02700 POLYGON.
02800
02900 _____________________________________________
03000 word | CW | CCW |
03100 0 | polygon ring |
03200 _____|___________________|___________________|
03300 word | DAD | SON |
03400 1 | level | 1st vector |
03500 _____|___________________|___________________|
03600 word | TYPE | RELOC |
03700 2 | 10 | 333 233 |
03800 _____|___________________|___________________|
03900 word | | |
04000 3 | ENDO | EXO |
04100 _____|___________________|___________________|
04200 word | | |
04300 4 | ARC | NCNT |
04400 _____|___________________|___________________|
04500 word | | |
04600 5 | NGON | PGON |
04700 _____|___________________|___________________|
04800 word | | |
04900 6 | NTIME | PTIME |
05000 _____|___________________|___________________|
00100 VECTOR/ARC/VERTEX.
00200
00300 The most numerous kind of node is the VECTOR/ARC/VERTEX,
00400 which for informal discussion will be called a VERTEX.
00500
00600 Vertices carry the fundamental geometric datum of an image locus. The
00700 image locus is stored in halfword positions named ROW and COL, which
00800 contain the row and column of a point in units 1/64 of a pixel. A
00900 "pixel" is a "picture element".
01000
01100 Vertices when used as vectors or arcs also carry the fundamental
01200 photometric datum of edge contrast. The fundamental data comes almost
01300 directly from the video image and is used to compute other data such
01400 as face area and region gradient.
01500
01600 Vertices always belong to a polygon node, whoes address is stored in
01700 the link named PGON; as members of a polygon the vertices form a
01800 perimeter or loop which is always connected so that each vertex has a
01900 neighboring vertex in the clockwise and in the counter clockwise
02000 directions about the polygons perimeters. There perimeter pointers
02100 are stored in teh link positions named CW and CCW.
00100 EDGE.
00200
00300 _____________________________________________
00400 word | NCW clockwise NCW |
00500 0 | wings |
00600 _____|___________________|___________________|
00700 word | NCCW counter PCCW |
00800 1 | clockwise wings |
00900 _____|___________________|___________________|
01000 word | TYPE | RELOC |
01100 2 | 2 | 400 000 |
01200 _____|___________________|___________________|
01300 word | | |
01400 3 | NFACE | PFACE |
01500 _____|___________________|___________________|
01600 word | | |
01700 4 | NED | PED |
01800 _____|___________________|___________________|
01900 word | | |
02000 5 | NVT | PVT |
02100 _____|___________________|___________________|
02200 word | | |
02300 6 | NTIME | PTIME |
02400 _____|___________________|___________________|
02500
02600
02700 WINGED EDGE MANDALA:
02800
02900 \ /
03000 nccw \ / pcw
03100 \ /
03200 ⊗ pvt
03300 |
03400 nface E pface
03500 |
03600 nvt ⊗
03700 / \
03800 ncw / \ pccw
03900 / \
00100 FACE.
00200
00300 _____________________________________________
00400 word | CW | CCW |
00500 0 | vector ring |
00600 _____|___________________|___________________|
00700 word | | |
00800 1 | | |
00900 _____|___________________|___________________|
01000 word | TYPE | RELOC |
01100 2 | 1 | 303 313 |
01200 _____|___________________|___________________|
01300 word | | |
01400 3 | | |
01500 _____|___________________|___________________|
01600 word | | |
01700 4 | | |
01800 _____|___________________|___________________|
01900 word | | |
02000 5 | | |
02100 _____|___________________|___________________|
02200 word | | |
02300 6 | NTIME | PTIME |
02400 _____|___________________|___________________|
02500
02600
02700 FILM.
02800
02900 _____________________________________________
03000 word | CW | CCW |
03100 0 | vector ring |
03200 _____|___________________|___________________|
03300 word | | |
03400 1 | | |
03500 _____|___________________|___________________|
03600 word | TYPE | RELOC |
03700 2 | 1 | 303 313 |
03800 _____|___________________|___________________|
03900 word | | |
04000 3 | | |
04100 _____|___________________|___________________|
04200 word | | |
04300 4 | | |
04400 _____|___________________|___________________|
04500 word | | |
04600 5 | | |
04700 _____|___________________|___________________|
04800 word | | |
04900 6 | NTIME | PTIME |
05000 _____|___________________|___________________|
00100 IMAGE.
00200
00300 _____________________________________________
00400 word | CW | CCW |
00500 0 | image ring |
00600 _____|___________________|___________________|
00700 word | DAD | SON |
00800 1 | film | level |
00900 _____|___________________|___________________|
01000 word | TYPE | RELOC |
01100 2 | 40 | 333 333 |
01200 _____|___________________|___________________|
01300 word | face ring |
01400 3 | NFACE | PFACE |
01500 _____|___________________|___________________|
01600 word | edge ring |
01700 4 | NED | PED |
01800 _____|___________________|___________________|
01900 word | vertex ring |
02000 5 | NVT | PVT |
02100 _____|___________________|___________________|
02200 word | | |
02300 6 | NTIME | PTIME |
02400 _____|___________________|___________________|
02500
02600
02700 LEVEL.
02800
02900 _____________________________________________
03000 word | CW | CCW |
03100 0 | level ring |
03200 _____|___________________|___________________|
03300 word | DAD | SON |
03400 1 | image | polygon |
03500 _____|___________________|___________________|
03600 word | TYPE | RELOC |
03700 2 | 1 | 303 313 |
03800 _____|___________________|___________________|
03900 word | | |
04000 3 | | |
04100 _____|___________________|___________________|
04200 word | | |
04300 4 | | |
04400 _____|___________________|___________________|
04500 word | | |
04600 5 | | |
04700 _____|___________________|___________________|
04800 word | | |
04900 6 | NTIME | PTIME |
05000 _____|___________________|___________________|
00100 THE CRE ALGORITHM.
00200
00300
00400 In the large, CRE consists of five steps: thresholding,
00500 contouring, smoothing, bundling and comparing. The first four large
00600 steps perform conversions between five kinds of images: 6-bit
00700 raster image, 1-bit raster image, rectangular contour image, arc
00800 contour image, and winged edge image. Comparing happens all along the
00900 process as will be explained.
01000
01100 1. THRESHOLDING: 6-BIT-IMAGE → 1-BIT-IMAGES.
01200 2. CONTOURING: 1-BIT-IMAGES → VIC-IMAGE.
01300 3. SMOOTHING: VIC-IMAGE → ARC-IMAGE.
01400 4. BUNDLING: ARC-IMAGE → WINGED-IMAGE.
01500
01600 Thresholding, the first and easiest step, consists of two subroutines:
01700
01800 1. THRESH: CUT,TVBUF → PAC
01900 2. PACXOR: PAC → HSEG,VSEG
02000
02100 The subroutine THRESH takes an integer argument, 0 < CUT ≤ 63, and
02200 for each pixel in the TVBUF with value equal to or greater than the
02300 cut THRESH sets a bit in PAC. PAC (picture accumulator) is a bit
02400 array of 216 rows by 288 columns which takes 1728 words in the TVSEG.
02500
02600 The subroutine PACXOR first copies the PAC into two slightly larger
02700 bit arrays named HSEG and VSEG, then it exclusive OR's the PAC,
02800 properly displaced one row or one column, into HSEG and VSEG to
02900 compute the horizontal and vertical border bits of blobs in the PAC.
03000
03100
00100 CONTOURING.
00200
00300 Contouring, the next major step, converts the bit arrays HSEG
00400 and VSEG into a node-link data structure that represents an equal
00500 intensity level contour map. Of such contouring, there be two minor
00600 steps: one, that of tracing the contour as a ring of vectors to form
00700 a polygon; and two, that of placing the polygon in the contour tree
00800 data structure.
00900
01000 Although the notion of a contour
01100 map is familiar to everyone as a piece of paper from the Geodetic
01200 Survey Office; implementing the notion into a data structure becomes
01300 a magical mystery tour. Two of the contouring mysteries to be
01400 discussed are jaggies and nesting. The jaggies problem involves doing
01500 something to a rectilinear quantized set of segments, to make its
01600 linear nature more evident. The jaggies solution in CRE is called
01700 the dekinking, and merely involves vernier positioning the
01800 right-turns as will be explained below.
01900
02000 A JAGGY ILLUSTRATED.
02100
02200 ___
02300 |___
02400 |____
02500 |___
02600 |___
02700
02800 The nesting problem involves comparing two polygons and deciding
02900 whether one is within the other; although easy in an isolated case,
03000 solving alot of nesting becomes very expensive in compute time or in
03100 memory space. The nesting solution in CRE is a fast big memory one
03200 involving a 62K array, called the SKYSEG.
03300
03400
03500 SMOOTHING.
03600
03700 BUNDLING.
00100 ALPHABETIC SUMMARY OF CRE TELETYPE COMMANDS.
00200
00300
00400 "A" Toggle Arc Make flag.
00500 "B" Drive the cart backwards.
00600 "C" Cut intensity level.
00700
00800 "D" Toggle baby polygon delete flag.
00900 "E" Select Edge Display.
01000 "F" Drive the cart forwards.
01100
01200 "G"
01300 "H" Display histogram.
01400 "I" Input TV picture from a disk file.
01500
01600 "J" Contour TV image at levels 6% from ends of histogram.
01700 "K" Toggle Krakauer flag.
01800 "L" Set cart steering to hard left position.
01900 "αL" Pan cart camera to the left.
02000
02100 "M"
02200 "N" Next image.
02300 "O" Output CRE file.
02400 "αO" Output TV file.
02500 "P" Plot file output to disk the current III display buffer.
02600
02700 "Q" Contour TV image at equally spaced levels.
02800 "R" Set cart steering to hard right position.
02900 "αR" Pan cart camera to the right.
03000 "S" Select camera number.
03100
03200 "T" Take 4-bit television picture.
03300 "αT" Take 6-bit television picture.
03400 "U" Toggle KILVIC enable flag.
03500 "V" Enter cart diagnostic sub command mode.
03600
03700 "W" Alter Arc width table.
03800 "X" Exit job.
03900 "Y" Display arc-contour.
04000 "αY" Display both-contour.
04100 "βY" Display vector-contour.
04200 "εY" Display vector contour without dekinking.
04300
04400 "Z" Zero data structure.
04500 "αZ" Zoom Reset to initial display position.
00100 BASIC SET OF COMMANDS.
00200
00300 "T" Take a 4-bit television picture.
00400 "Q" Make CRE picture, from three intensity cuts.
00500 "αO" Output CRE file.
00600
00700 LINK FOLLOWING COMMANDS & THE DIAGONOSTIC NODE DISPLAY.
00800
00900 These 14 commands allow detailed inspection of the CRE data
01000 structure by showing the contents of a node. Data halfwords of a node
01100 are displayed as six octal digits; link halfwords are displayed prefixed
01200 with a letter indicating the type of node being pointed at; a zero
01300 link is displayed as "NIL".
01400
01500 The FILM node, which is the root of the whole data structure is fetched
01600 and displayed by the "+" command. From the Film, the ">" command can
01700 be used to get SON(FILM) which is always the first image, and ">" command
01800 of an image will get a level and ">" of a level will get a polygon.
01900 Now vectors, polygons, edges and faces are intensified when their contents
02000 are being displayed. The exit command is "!", which leaves the screen less
02100 cluttered.
02200
02300
02400
02500 "+" Fetch Film Node.
02600 "!" Flush diagonostic node display.
02700
02800
02900 0 "," "." CW,,CCW
03000 1 "<" ">" DAD,,SON
03100 2 There is never a link at this word.
03200 3. "↓" "↑" NFACE,,PFACE or ENDO,,EXO
03300 4. "≤" "≥" NED,,PED or ARC,,PED
03400 5. "←" "→" NVT,,PVT or NGON,,PGON
03500 6. "⊂" "⊃" NTIME,,PTIME
00100 DISPLAY WINDOW SCROLLING COMMANDS.
00200
00100 OPERATIONAL SUMMARY OF CRE TELETYPE COMMANDS.
00200
00300 INPUT/OUTPUT.
00400
00500 CART-CONTROL.
00600
00700 DISPLAY-CONTROL.
00800
00900 CONTOURING.
01000 "C" cut at level.
01100 "Q" equally spaced contours.
01200 "J" Make two contour with respect to per centage from
01300 ends of histogram.
01400
01500 "Q" - 3 CUTS: 20, 40, 60.
01600 "αQ" - 7 CUTS: 10, 20, 30, 40, 50, 60, 70.
01700 "βQ" - 8 CUTS: 04, 14, 24, 34, 44, 54, 64, 74.
01800 "εQ" - 15 CUTS: 04,10,14,20,24,30,34,40,44,50,54,60,64,70,74.
00100 CART CONTROL COMMANDS & OPERATING THE CART.
00200
00300 There are seven cart commands: drive forwards, drive
00400 backwards, turn left, turn right, pan camera left, pan camera right
00500 and halt:
00600
00700 "F" Drive Cart Forwards for one minute.
00800 "B" Drive Cart Backwards for one minute.
00900 "L" Turn steering wheels hard to left.
01000 "R" Turn steering wheels hard to right.
01100 "αL" Pan camera to the left for 10 seconds.
01200 "αR" Pan camera to the right for 10 seconds.
01300 " " Halt and continue spacewar job on PDP-6.
01400 "0" Halt and continue spacewar job on PDP-6.
01500 carriage return - Halt and stop spacewar job on PDP-6.
01600
01700
01800 First and most important is understanding how to stop the cart. The
01900 teletype halt command is " ", spacebar, or "0"; also any character
02000 other than "F", "B", "L", or "R" will stop the cart. Cart commands
02100 are passed first from a teletype to the PDP-10, then to the PDP-6,
02200 then over a citizens band, 27.045 megahertz, radio link to the cart
02300 control logic; and so when communications are lacking between
02400 entities in the chain of command the lower entities times out and
02500 causes the cart to halt. The cart control logic times out in a fifth
02600 of a second if it does not hear from the PDP-6; the PDP-6 times out
02700 in less than a minute if it has not heard from the PDP-10; the PDP-6
02800 also stops broadcasting cart commands if it detects the death of the
02900 PDP-10; the PDP-10 job times out after 5 minutes of not hearing
03000 from the teletype and kills the PDP-6 spacewar job.
03100
00100 II. FILE FORMATS.
00200 A. Television Image Format.
00300 B. Region/Edge Image Format.
00400
00500 A. Television Image Format.
00600
00700 The standard Cart's Eye television image is
00800 216 rows of 288 columns of 4 bits per pixel.
00900
01000 B. Contour/Region/Edge Image Format.
01100
01200 The image format, CRE, is essentially a core dump
01300 of CRE's internal node/link data structure. There are eight kinds
01400 of nodes and the nodes are fixed sized at six words per node.
01500
01600 From the top, the first node of a file is always a "FILM" node.
01700 The head of a film node points to a ring of "IMAGE" nodes.
01800 The head of an image node points to a ring of "LEVEL" nodes.
01900 The head of a level node points to a ring of "POLYGON" nodes.
02000 The head of a polygon node points to a ring of "EDGE" nodes.
02100 And edge nodes do not have a head pointer. Which is equivalent to
02200 saying that a file contains a film, a film is composed of images, an
02300 image is composed of levels, a level is composed of polygons and a
02400 polygon is composed of edges.
02500
02600 Now the detailed explanation will proceed bottom-up, starting
02700 with the most numerous edge nodes.
02800
02900 File names are accepted in the usual DEC format of name, dot,
03000 extension, left square bracket, project, comma, programmer, right
03100 square bracket, carriage return line feed. Where the filename is from
03200 one to six characters; and the extension project and programmer are
03300 from one to three characters. Everything but the filename is
03400 optional.
00100 IV. PERFORMANCE.
00200
00300 V. LISP AND SAIL INTERFACING.
00400 VI. EDITORIAL REMARKS.
00500
00600
00700 1.
00800 The version of CRE discussed in this document is known to
00900 me as the third, or the version of Christmas-72. CRE-I of '68 and
01000 '69 was embedded in LISP and contained thresholding, bit raster
01100 operations, and a polygon trace routine. CRE-II was embedded in
01200 SAIL, and in early forms even used LEAP. Both CRE-I and CRE-II
01300 were built around the notion of "windowing". CRE-IV, of
01400 Thanksgiving-72 was was scan line oriented.
01500
01600
01700 3.
01800 It is my impression that all the so called "scientific" ideas
01900 in CRE have appeared elsewhere. In particular, I was aware of and
02000 kind of liked the work of Krakauer, Zahn, and Mc Cormick's
02100 ILLAIC-III. Also, I was aware of and disliked the work of Pingle and
02200 Hueckel. I wish to acknowledge all these people from whom I have
02300 borrowed ideas, both positive and negative. On the other hand, I
02400 alone wrote and developed all the code in CRE.
02500
02600 4.
02700 Future CRE feature might include, a window version, image
02800 comparison, and MAKVID.
02900
03000 5. Prejudiced and Unprejudiced Vision.
00100 APPENDIX.
00200
00300 The CRE code uses additional PDP-10 mnemonics for the sake
00400 of pronouciation and brevity. The mnemonics stem from ancient PDP-1
00500 nomenclature; in the PDP-10 the left half word is the instruction
00600 part and the right half word is the address part. The codes CAR and
00700 CDR are traditional LISP names, derived from IBM-709 nomenclature;
00800 CAR and CDR are appropriate PDP-6/10 op codes because according to
00900 Kotok,the machine was designed to facillate LISP.
01000
01100 HLR LIP Load Instruction Part.
01200 HRR LAP Load Address Part.
01300 HRLM DIP Deposit in Instruction Part.
01400 HRRM DAP Deposit in Instruction Part.
01500
01600 HRRZS ZIP Zero Instruction Part.
01700 HLLZS ZAP Zero Address Part.
01800 HRROS WIP W'ones to Instruction Part.
01900 HLLOS WAP W'ones to Address Part.
02000
02100 HLRZ CAR Contents Address Register.
02200 HRLI LIPI Load instruction part immediate.
02300 HRRI LAPI Load address part immediate.
02400 HRLZM DIPZ Deposit into instruction part with zeroes.
02500
02600 HRRZ CDR Contents Decrement Register.
02700 MOVEI LACI Load Accumulator Immediate.
02800 MOVSI SLACI Swap Load Accumulator Immediate.
02900 HRRZM DAPZ Deposit into Address part with zeroes.
03000
03100 MOVE LAC Load Accumulator.
03200 MOVN LACN Load Accumulator Negative.
03300 MOVM LACM Load Accumulator Magnitude.
03400 MOVS SLAC Swap Load Accumulator.
03500
03600 MOVEM DAC Deposit Accumulator into memory.
03700 MOVNM DACN Deposit Accumulator negative.
03800 MOVMM DACM Deposit Accumulator magnitude.
03900 MOVSM SDAC Swap Deposit Accumulator.
04000
04100 HLRE NIP Number from instruction part.
04200 HRRE NAP Number from address part.
04300 HRREI NIM Number immediate.
04400 JRST GO Load program counter immediate.